home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 3 / BBS in a box - Trilogy III.iso / Files / Prog / D-G / GemsI / Original / BoundingSphere.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-06-16  |  3.7 KB  |  137 lines  |  [TEXT/MPS ]
  1. /*
  2. An Efficient Bounding Sphere
  3. by Jack Ritter
  4. from "Graphics Gems", Academic Press, 1990
  5. */
  6.  
  7. /* Routine to calculate tight bounding sphere over    */
  8. /* a set of points in 3D */
  9. /* This contains the routine find_bounding_sphere(), */
  10. /* the struct definition, and the globals used for parameters. */
  11. /* The abs() of all coordinates must be < BIGNUMBER */
  12. /* Code written by Jack Ritter and Lyle Rains. */
  13.  
  14. #include <stdio.h>
  15. #include <math.h>
  16. #include "GraphicsGems.h"
  17.  
  18. #define BIGNUMBER 100000000.0          /* hundred million */
  19. struct Point3Struct {double x,y,z;};  /* The only struct used. */
  20.  
  21. /* GLOBALS. These are used as input and output parameters. */
  22.  
  23. struct Point3Struct caller_p,cen;
  24. double rad;
  25. int NUM_POINTS;
  26.  
  27. /* Call with no parameters. Caller must set NUM_POINTS */
  28. /* before calling. */
  29. /* Caller must supply the routine GET_iTH_POINT(i), which loads his */
  30. /* ith point into the global struct caller_p. (0 <= i < NUM_POINTS). */
  31. /* The calling order of the points is irrelevant. */
  32. /* The final bounding sphere will be put into the globals */
  33. /* cen and rad. */
  34.  
  35.  
  36. find_bounding_sphere()
  37. {
  38. register int i;
  39. register double dx,dy,dz;
  40. register double rad_sq,xspan,yspan,zspan,maxspan;
  41. double old_to_p,old_to_p_sq,old_to_new;
  42. struct Point3Struct xmin,xmax,ymin,ymax,zmin,zmax,dia1,dia2;
  43.  
  44.  
  45. /* FIRST PASS: find 6 minima/maxima points */
  46. xmin.x=ymin.y=zmin.z= BIGNUMBER; /* initialize for min/max compare */
  47. xmax.x=ymax.y=zmax.z= -BIGNUMBER;
  48. for (i=0;i<NUM_POINTS;i++)
  49.     {
  50.     GET_iTH_POINT(i); /* load global struct caller_p with */
  51.                     /* his ith point. */
  52.     if (caller_p.x<xmin.x)
  53.         xmin = caller_p; /* New xminimum point */
  54.     if (caller_p.x>xmax.x)
  55.         xmax = caller_p;
  56.     if (caller_p.y<ymin.y)
  57.         ymin = caller_p;
  58.     if (caller_p.y>ymax.y)
  59.         ymax = caller_p;
  60.     if (caller_p.z<zmin.z)
  61.         zmin = caller_p;
  62.     if (caller_p.z>zmax.z)
  63.         zmax = caller_p;
  64.     }
  65. /* Set xspan = distance between the 2 points xmin & xmax (squared) */
  66. dx = xmax.x - xmin.x;
  67. dy = xmax.y - xmin.y;
  68. dz = xmax.z - xmin.z;
  69. xspan = dx*dx + dy*dy + dz*dz;
  70.  
  71. /* Same for y & z spans */
  72. dx = ymax.x - ymin.x;
  73. dy = ymax.y - ymin.y;
  74. dz = ymax.z - ymin.z;
  75. yspan = dx*dx + dy*dy + dz*dz;
  76.  
  77. dx = zmax.x - zmin.x;
  78. dy = zmax.y - zmin.y;
  79. dz = zmax.z - zmin.z;
  80. zspan = dx*dx + dy*dy + dz*dz;
  81.  
  82. /* Set points dia1 & dia2 to the maximally seperated pair */
  83. dia1 = xmin; dia2 = xmax; /* assume xspan biggest */
  84. maxspan = xspan;
  85. if (yspan>maxspan)
  86.     {
  87.     maxspan = yspan;
  88.     dia1 = ymin; dia2 = ymax;
  89.     }
  90. if (zspan>maxspan)
  91.     {
  92.     dia1 = zmin; dia2 = zmax;
  93.     }
  94.  
  95.  
  96. /* dia1,dia2 is a diameter of initial sphere */
  97. /* calc initial center */
  98. cen.x = (dia1.x+dia2.x)/2.0;
  99. cen.y = (dia1.y+dia2.y)/2.0;
  100. cen.z = (dia1.z+dia2.z)/2.0;
  101. /* calculate initial radius**2 and radius */
  102. dx = dia2.x-cen.x; /* x componant of radius vector */
  103. dy = dia2.y-cen.y; /* y componant of radius vector */
  104. dz = dia2.z-cen.z; /* z componant of radius vector */
  105. rad_sq = dx*dx + dy*dy + dz*dz;
  106. rad = sqrt(rad_sq);
  107.  
  108. /* SECOND PASS: increment current sphere */
  109.  
  110. for (i=0;i<NUM_POINTS;i++)
  111.     {
  112.     GET_iTH_POINT(i); /* load global struct caller_p  */
  113.                     /* with his ith point. */
  114.     dx = caller_p.x-cen.x;
  115.     dy = caller_p.y-cen.y;
  116.     dz = caller_p.z-cen.z;
  117.     old_to_p_sq = dx*dx + dy*dy + dz*dz;
  118.     if (old_to_p_sq > rad_sq)     /* do r**2 test first */
  119.         {     /* this point is outside of current sphere */
  120.         old_to_p = sqrt(old_to_p_sq);
  121.         /* calc radius of new sphere */
  122.         rad = (rad + old_to_p) / 2.0;
  123.         rad_sq = rad*rad;     /* for next r**2 compare */
  124.         old_to_new = old_to_p - rad;
  125.         /* calc center of new sphere */
  126.         cen.x = (rad*cen.x + old_to_new*caller_p.x) / old_to_p;
  127.         cen.y = (rad*cen.y + old_to_new*caller_p.y) / old_to_p;
  128.         cen.z = (rad*cen.z + old_to_new*caller_p.z) / old_to_p;
  129.         /* Suppress if desired */
  130.         printf("\n New sphere: cen,rad = %f %f %f   %f",
  131.             cen.x,cen.y,cen.z, rad);
  132.         }    
  133.     }
  134. }              /* end of find_bounding_sphere()  */
  135.  
  136.  
  137.